package com.mlick.a.leetcode;

import cn.leetcode.base.ListNode;

import static cn.MainClass.listNodeToString;
import static cn.MainClass.stringToListNode;

/**
 * @author lixiangxin
 * @date 2019/3/21 10:05
 **/
public class LC21 {


    public static void main(String[] args) {

        ListNode l1 = stringToListNode("1,1,1,7");
        ListNode l2 = stringToListNode("2,3,4,5,6,7,8");


        ListNode ret = new LC21().mergeTwoLists2(l1, l2);
        String out = listNodeToString(ret);
        System.out.println(out);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }


    private ListNode mergeTwoLists1(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);
        ListNode next = head;
        ListNode node = l1;
        ListNode node2 = l2;
        while (node != null) {
            next.next = node;
            next = next.next;
            node = node.next;
        }

        while (node2 != null) {
            next.next = node2;
            next = next.next;
            node2 = node2.next;
        }

        return head.next;
    }

    private ListNode mergeTwoLists2(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (l1 != null && l2 != null) {

            if (l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }

            cur = cur.next;
        }

        cur.next = l1 != null ? l1 : l2;

        return head.next;
    }



}
